package leetcode_900;

/**
 *@author 周杨
 *SuperEggDrop_887_ 在某层丢鸡蛋的测试 问最少能用多少步测出所有层数的可能
 *describe:用动态规划 AC 45%
 *2018年11月11日 下午5:15:37
 */
public class SuperEggDrop_887_ {
	public static void main(String[] args) {
		SuperEggDrop_887_ test=new SuperEggDrop_887_();
		System.out.println(test.superEggDrop(3, 14));
	}
	
	
	public int superEggDrop(int K, int N) {
        int dp[][]=new int[N+1][K+1];//表示K个鸡蛋 在N步能测出的最大层数
        for (int m = 1; m <= N; m++) {
            for (int k = 1; k <= K; k++) {
            	//如果在当在此状态扔鸡蛋 在某层碎了 那么最多确定dp[m-1][k-1]步
            	//如果没有碎 那么dp[m-1][k]
                dp[m][k] = dp[m-1][k] + dp[m-1][k-1] + 1;
                if (dp[m][k] >= N) {
                    return m;
                }
            }
        }
        return N;
    }
	
	
	/**
	 * describe:动态规划 超时 79/121
	 * 2018年11月11日 下午5:31:44
	 */
	public int superEggDrop1(int K, int N) {
        int dp[][]=new int[K+1][N+1];//dp[i][j]表示用i个鸡蛋测j层的最优步数
        for(int i=0;i<=N;++i) {//初始化状态转移方程
        	//dp[i][0]=0; 没有鸡蛋 
        	dp[1][i]=i;//1个鸡蛋测i层
        }
        for(int i=2;i<=K;++i) {//i表示有几个鸡蛋
        	for(int j=1;j<=N;++j) {
        		dp[i][j]=j;//最差的情况是丢j层
        		for(int k=1;k<j;++k) {//我们枚举 从哪些楼丢鸡蛋
        			//如果这一层破了 那么我们需要用dp[i-1][j-1]
        			//如果这一层没破 那么我们需要用dp[i][N-j]
        			dp[i][j]=Math.min(dp[i][j], Math.max(dp[i-1][k-1], dp[i][j-k])+1);
        		}
        	}
        }
        return dp[K][N];
    }
}
